# -*- coding: utf-8 -*-
"""
Created on Thu Sep 12 16:31:30 2019

@author: Administrator
"""

# 1035 插入与归并
# 题目保证每组测试的结果是唯一的
# 思路：
# 首先因为结果唯一，所以不是插入，就是归并。
# 通过特征判断中间结果是那种排序。插入的特征明显：前部分有序，后部分无序。
# 判断出排序类型后，通过中间结果，来给出下一轮迭代的排序中间结果

# 步骤：
# 判断是否为插入排序
# 如果是插入排序，迭代一次插入排序
# 因为结果唯一，否则就是归并排序
# 如果是归并排序，判断出当前是第几代，再迭代一次


# 测试用例：
# 1.只有一个数，结果不唯一，不存在
# 2.两个数，如3,8 结果不唯一，不存在
# 3.中间结果是顺序排序，如，1,2,3,4,5，结果不唯一，不存在


def test():
    num = int(input())
    start_raw = str(input()).split(' ')
    temp_raw = str(input()).split(' ')
    
    start = []
    temp = []
    
    for i in range(num):
        start.append(int(start_raw[i]))
        temp.append(int(temp_raw[i]))
    
    # 判断是否为插入排序
    if is_insert(temp, start):
        print("Insertion Sort")
        # 如果是插入排序，迭代一次插入排序
        temp = insert_sort(temp)
        print_list(temp)
    else:
        # 因为结果唯一，否则就是归并
        print("Merge Sort")
        # 如果是归并排序，判断出当前是第几代，再迭代一次
        temp = merge_sort(temp)
        print_list(temp)

test()

def is_insert(temp_list, start_list):
    """判断是否为插入操作
    逻辑：数据分为两段，之前一段有序，后半段和原始元素相同
    """
    length = len(temp_list)
    current_min = min(temp_list)
    
    for i in range(length):
        if temp_list[i] >= current_min:
            current_min = temp_list[i]
        else:
            # 记录分界位置
            divide = i
            break
    
    for j in range(divide,length):
        if temp_list[j] != start_list[j]:
            return False
    return True

#start_list = [3, 1, 2, 8, 7, 5, 9, 4, 6, 0]
#temp_list = [1, 2, 3, 7, 8, 5, 9, 4, 6, 0]
#start_list = [3, 1, 2, 8, 7, 5, 9, 4, 0, 6]
#temp_list = [1, 3, 2, 8, 5, 7, 4, 9, 0, 6]
#print(is_insert(temp_list, start_list))
    

def insert_sort(temp_list):
    """根据插入排序的中间结果，进行下一轮插入排序
    """
    length = len(temp_list)
    current_min = min(temp_list)
    
    for i in range(length):
        if temp_list[i] >= current_min:
            current_min = temp_list[i]
        else:
            # 寻找分界位置
            divide = i
            break
    
    temp = temp_list[divide]
    end = divide-1
    current = divide
    # 从尾到头找合适位置插入
    for j in range(end,-1,-1):
        if temp_list[j] > temp:
            # 后移
            temp_list[current] = temp_list[j]
            current -= 1
        else:
            temp_list[current] = temp

    return temp_list

#temp_list = [1, 2, 3, 7, 8, 5, 9, 4, 6, 0]
#print(insert_sort(temp_list))

def merge_sort(temp_list):
    """根据归并排序的中间结果，返回下一轮归并排序的结果
    """
    # 初始化当前归并次数
    current = 1
    label = '<'
    final_list = []
    while True:
        # 按照当前归并次数划分子集
        divided_set = []
        divided_set = divide_subset(temp_list, current)
        # 遍历子集
        result = is_ordered_divided_set(divided_set, label)
        # 如果有序，获取当前归并级别current和子集，再进行一次归并
        if result == True:
            last_divided_set = divided_set
            current += 1
            continue
        # 如果无序，当前归并级别+1，再进行一次循环
        else:
            again_list = merge_again(last_divided_set, label)
            break
    
    for ele in again_list:
        final_list += ele
    
    return final_list

#temp_list = [2,4,3,6,1]
#temp_list = [1, 3, 2, 8, 5, 7, 4, 9, 0, 6]
#print(merge_sort(temp_list))


def is_ordered_divided_set(divided_set, label):
    
    for sub in divided_set:
        # 判断在子集内元素是否有序
        temp_result = is_ordered(sub, label)
        if temp_result != True:
            return False
    
    return True

#divided_set = [[1,2],[3,4],[5,7]]
#
#print(is_ordered_divided_set(divided_set, '<'))

def divide_subset(temp_list, current):
    """按照每组current个元素划分子集
    temp_list:原集合
    current:每组元素数
    """
    divided_set = []
    temp = []
    
    for ele in temp_list:
        
        temp.append(ele)
        
        if len(temp) == current:
            # 满足current要求加入集合
            divided_set.append(temp)
            temp = []

    # 最后不够一组时，直接加入divided_set
    if len(temp) != 0:
        divided_set.append(temp)
    
    return divided_set

#temp_list = [3,2,1,4,5,6]
#print(divide_subset(temp_list, 4))
#divided_set = divide_subset(temp_list, 3)
    
def is_ordered(sub, label):
    """判断子集是否有序
    label:正序或者逆序的标识
    sub:集合
    """
    
    if label == '<':
        sorted_sub = sorted(sub)
        if sorted_sub == sub:
            return True
    elif label == '>':
        sorted_sub = sorted(sub, reverse=True)
        if sorted_sub == sub:
            return True
    return False

#print(is_ordered(divided_set[0], '>'))

def merge_again(divided_set, label):
    
    # 相邻的两个集合合并
    length = len(divided_set)
    result = []
    for i in range(0,length,2):
        # 如果下标到达最后一个元素，并且为偶数
        if (i == length - 1) and i % 2 == 0:
            result.append(divided_set[i])
        else:
            if label == '<':
                result.append(sorted(divided_set[i] + divided_set[i+1]))
            elif label == '>':
                result.append(sorted((divided_set[i] + divided_set[i+1]), reverse=True))
    
    return result            

#divided_set = [[3,2],[5,1],[6,8],[10,13]]
#print(merge_again(divided_set, '<'))

# list的运算
# 逻辑运算：
# [] == [] True
# [] > [2] False
# [] < [2] True
# list的大小比较以长度优先，后数值优先
# 越长越大、长度相同的，数值越大越大
# 算术运算
# [2] + [1] = [2,1]  加号被重载，可用于list的合并

def print_list(data_list):
    result = ""
    for i in range(len(data_list)):
        result += "%d " % data_list[i]
    
    print(result[0:-1])

#print_list([1,2,3,4])